package com.kizuki.algorithm.leetcode;

public class 手撕快速排序 {

    public void quickSort(int[] arr, int start, int end) {
        if (start >= end) {
            return;
        }
        int key = arr[start];
        int left = start;
        int right = end;
        while (left < right) {
            while (left < right && arr[right] >= key) {
                right--;
            }
            if (left < right) {
                arr[left++] = arr[right];
            }
            while (left < right && arr[left] <= key) {
                left++;
            }
            if (left < right) {
                arr[right--] = arr[left];
            }
        }
        arr[left] = key;
        quickSort(arr, start, left - 1);
        quickSort(arr, left + 1, end);
    }

}
